import java.util.ArrayList;
import java.util.List;

public class Leetcode234 {
    public static void main(String[] args) {
        ListNode test = new ListNode();
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(0);
        list.add(1);
        ListNode.createNode(test, list);
        System.out.println(isPalindrome(test));
    }

    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        if (fast != null) {
            slow = slow.next.next;
        }

        for (ListNode i = slow; i != null; i = i.next) {
            if (i.val == head.val) {
                head = head.next;
            } else {
                return false;
            }
        }

        return true;
    }
}
